package 校招笔试.字节;

import org.junit.Test;
import 校招笔试.恒生电子.T;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/21 9:31
 */
public class lc求助 {
    /*
     https://leetcode.cn/circle/discuss/fbhhev/

     md 题都读错了, **可以重复选**
     这个题, 不容易的!
     */

    public int solve(int nums[], int value) {
        this.compare = value;
        this.len = String.valueOf(value).length();
        dfs(0, 0, nums, new boolean[nums.length]);
        return max;
    }

    private int max;
    private int compare;
    private int len;
    private static int TEN = 10;

    public void dfs(int index, int path_sum, int nums[], boolean used[]) {
//        if(path_sum >=  compare){
//            return ;
//        }
//        max = Math.max(max,path_sum);
        if (index == len) {  // 之前的写法，可能比较丑陋
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                int temp = nums[i] * (int) Math.pow(TEN, index);
                if (path_sum + temp < compare) {
                    dfs(index + 1, path_sum + temp, nums, used);
                    max = Math.max(max, path_sum + temp);
                }
                used[i] = false;
            }
        }
    }




    /*
     倒序 遍历 len 个长度求和
     */
    public int for_each(int nums[],int len){
        int ans = 0, n = nums.length - 1;
        for(int i = len - 1; i >= 0; i--,n--){
            ans += nums[n] * (int) Math.pow(TEN,i);
        }
        return ans;
    }



    @Test
    public void test() {
        int val = 2499;
        int nums[] = {1, 2, 4, 9};
//        int val = 1111;
//        int nums[] = {9, 2, 4, 9};
//        int val = 2229;
//        int nums[] = {2, 2,3, 4, 9};
        System.out.println(solve(nums, val));
        System.out.println(for_each(nums,2));
        System.out.println(slove_0(nums,val));
    }


    /*
     排序  + 二分 + 贪心的写法
     map 缓存
     思想很前卫
     */
    /*
      int val = 2499;
        int nums[] = {1, 2, 4, 9};
        不太对, 这个思路, 从上面这个basecase 去看一下 就明报了
     */
    public int slove_0(int nums[], int val) {
        String s_val = String.valueOf(val);
        int ans = 0 ,len_val = s_val.length();
        Arrays.sort(nums);
        if(nums.length < len_val){ // 直接 倒序 加完 数字即可

            return for_each(nums,nums.length);
        }
         final int UN_INIT = 10;
        //  需要组合
        /*
         简单的解释 下 next 的含义 : 优点类似于 KMP 的 next数组

         next[i] : 表示 的是  数字 <= i 当前对应的 nums数组中下标的位置
         eg next[2] = 0 表示 <= 2 的 **目前可选** 的 nums 中的下标 为 0位置

         eg: 如果 next[i] = -1 表示当前 <= i 的在 nums 中已经不存在了, 直接 for_each 了
         */
        int next[] = new int[10]; // 一定要注意 这个 next 数组再记录什么东西，很抽象， 具体在纸上 进行比划比划
        Arrays.fill(next,UN_INIT); // 把next 数组 标记成, 未初始化!
        for(int i = 0;i < s_val.length();i++){
            int v = s_val.charAt(i) - '0';
            int find = binary(nums,v);  // find  < x + 1
            /*
            eg1:  val = 1229
              nums [2,2,3,4,9]
              val 的第一个值, 根本就找不到 find = -1, 那直接 for_each


             eg2  val = 2229
             nums [2,2,3,4,7];
             -
              val第一个 2  find = 1;
              next[2] = UN_INIT , 所以 next[2] = find - 1 = 0;

             - val 第二个 2 find = 1
             但是 next[2] != UN_INIT  ,直接 使用next[2](此时next[2] = 0)即可(判断是否为 -1), 并且 把next[2]-- = -1

            - val 的第三个 2 find = 1
            但是 next[2] = -1 直接 for_each
             */
            if(find == -1 || next[v] == - 1){ // not found  || 或者已经找不到了
                return  for_each(nums,len_val - 1); // 直接 构造结果就行了
            }
            if(next[v] == UN_INIT){
                next[v] = find - 1;
                ans += nums[find] * (int)Math.pow(TEN,len_val - i - 1);
            }else{
                ans += nums[next[v]] * (int)Math.pow(TEN,len_val - i - 1);
                next[v]--;
            }
        }

        return ans;

    }
    /*
     这个二分 是在求 < x + 1 的最右边
     对于整数 而言  <= x  等价于  < x + 1
     */
    public int binary(int nums[],int val){
        int l = 0,  r = nums.length - 1;
        while(l < r){
            int mid = l + r + 1>> 1;
            if(nums[mid] > val){
                r = mid - 1;
            }else{
                l = mid;
            }
        }
        if(l == 0){
            l =  nums[l] < val ? l : - 1; // 判断一下边界的情况, 也就是找不到的情况 , 这种情况对于该题来说,很关键
        }
        return l;
    }

    /*
     简单的分解数字
     */
    public static void main(String[] args) {
        int val = 249910389;
        int count = 0;
        List<Integer> collect = new ArrayList<>();
        while (val != 0) {
            int mod = val % 10;
            collect.add(mod);
            count++;
            val /= 10;

        }

        System.out.println(count);
        System.out.println(collect);
        Collections.reverse(collect);
        System.out.println(collect);
    }

}
